/*************************************************************************
	> File Name: ./include/common.h
	> Author: zq
	> Mail: zhouquan1511@163.com 
	> Created Time: Wed 26 Apr 2023 09:08:17 PM CST
 ************************************************************************/

#pragma once

#include <iostream>
#include <vector>
#include <ctime>
#include <cassert>
#include <thread>
#include <mutex>
#include <algorithm>
#include <unordered_map>
#include <atomic>
#include "ObjectPool.h"

using std::cout;
using std::endl;

#ifdef _WIN64
	typedef unsigned long long PAGE_ID;//页号，8k为一个页面大小，2^32/2^13=2^19个页
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	//linux
#endif

#ifdef _WIN32
	#include <Windows.h>
#else
	#include <unistd.h>
	#include <sys/mman.h>
#endif

//一些固定参数
static const size_t MAX_BYTES = 256 * 1024; //thread_cache提供内存块的上限, 超过此值直接向page_cache或系统申请
static const size_t NFREELISTS = 208; //threadCache和centralCache中哈希桶的个数
static const size_t NPAGES = 128; //pageCache中哈希桶的个数
static const size_t PAGE_SHIFT = 13; //页大小转换偏移，一页为2^13=8kb

//向系统直接申请内存
inline static void* SystemAlloc(size_t kpage) {
#ifdef _WIN32
	void *ptr = VirtualAlloc(0, kpage<<13, MEM_COMMIT|MEM_RESERVE,
							PAGE_READWRITE);
#else
	void *ptr = mmap(NULL, kpage<<13, PROT_READ|PROT_WRITE,
					MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

//系统直接回收内存
inline static void SystemFree(void *ptr, size_t size) {
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	munmap(ptr, size);
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

//用于内存节点的连接
static void*& NextObj(void *ptr) {
	return (*(void**)ptr);
}

//自由链表：管理小块内存
class FreeList {
private:
	void *_freeList = nullptr;
	size_t _maxSize = 1; //控制thread_cache向central_cache申请的内存块的个数,用于慢开始反馈调节法
	size_t _size = 0;
public:	
	size_t& MaxSize() {
		return _maxSize;
	}
	
	size_t Size() {
		return _size;
	}

	//头插
	void Push(void *obj) {
		assert(obj);
		NextObj(obj) = _freeList;
		_freeList = obj;
		_size++;
	}

	//头删
	void* Pop() {
		void *obj = _freeList;
		_freeList = NextObj(obj);
		return obj;
		_size--;
	}

	//插入一段范围的对象[start,end]到链表中
	void PushRange(void *start, void *end, size_t n) {
		assert(start);
		assert(end);
		
		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}
	
	void PopRange(void *&start, void *&end, size_t n) {
		assert(n <= _size);
		
		start = _freeList;
		end = start;
		for (int i = 0; i < n - 1; i++) {
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}

	bool Empty() {
		return _freeList == nullptr;
	}
};

//管理以页为单位的大块内存，同时维护小块内存，直接提供给threadcache
struct Span {
	PAGE_ID _pageId = 0; //大块内存的起始页号
	size_t _n = 0; //页的数量

	Span *_prev = nullptr;
	Span *_next = nullptr;
	
	size_t objSize = 0; //切好的小块内存大小
	void *_freeList = nullptr; //大块内存切分形成的小块内存链表
	size_t _useCount = 0; //当前Span分配给threadcache的小块内存计数，用于归还pagecache
	bool _isUse = false; //当前Span是否被使用，即是否由centralCache管理
};

//双向Span链表，用于管理Span
//注意移除的Span需要将其归还给下层pageCache，因此不用delete
class SpanList {
	private:
		Span *_head;
		static ObjectPool<Span> _spanPool;
	public:
		std::mutex _mtx; //桶锁
		
		SpanList() {
			_head = _spanPool.New();
			_head->next = _head;
			_head->prev = _head;
		}

		Span* Begin() {
			return _head->_next;
		}
		
		Span* End() {
			return _head;
		}
		
		void Insert(Span *pos, Span *newSpan) {
			assert(pos);
			assert(newSpan);
			
			pos->_prev->_next = newSpan;
			newSpan->_prev = pos;
			newSpan->_next = pos;
			pos->_prev = newSpan;
		}

		void PushFront(Span *span) {
			Insert(Begin(), span);
		}

		void Erase(Span *pos) {
			assert(pos);
			assert(pos != _head);
			
			pos->_prev->_next = pos->_next;
			pos->_next->_prev = pos->_prev;
		}

		bool Empty() {
			return _head->_next == _head;
		}
		
		Span* PopFront {
			Span *front = Begin();
			Erase(front);
			return front;
		}
};

//管理对齐和映射关系
class SizeClass {
private:
public:
	
	//慢开始反馈台调节算法，控制threadCache向centralCache申请的内存个数
	//内存块申请个数上限, threadCache->centralCache 
	inline static NumMoveSize(size_t size) {
		assert(size > 0);
		
		int num = MAX_BYTES / size;
		
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;

		return num;
	}
	//Span页数申请上限，centralCache->pageCache
	inline static NumMovePage(size_t size) {
		size_t num = NumMoveSize(size);
		size_t nPage = num * size;
		nPage >>= PAGE_SHIFT;
		if (nPage == 0) {
			nPage = 1;
		}
		return nPage;
	}

	

	//整体控制在最多10%左右的内碎片浪费
	//[1,128]              8byte对齐       freelist[0,16)
	//[128+1,1024]         16byte对齐      freelist[16,72)
	//[1024+1,8*1024]      128byte对齐     freelist[72,128)
	//[8*1024+1,64*1024]   1024byte对齐    freelist[128,184)
	//[64*1024+1,256*1024] 8*1024byte对齐  freelist[184,208)
	//获取向上对齐后的字节数
	inline static size_t RoundUp(size_t bytes) {
		if (bytes <= 128) {
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024) {
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8*1024) {
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 64*1024) {
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256*1024) {
			return _RoundUp(bytes, 8*1024);
		}
		else {
			return _RoundUp(bytes, 1 << PAGE_SHIFT);
		}
	}

	inline static size_t _RoundUp(size_t bytes, size_t alignNum) {
		size_t alignSize = 0;
		if (bytes % alignNum != 0) {
			alignSize = (bytes / alignNum + 1) * alignNum;
		}
		else {
			alignSize = bytes;
		}
		return alignSize;
	}
	
	//获取对应哈希桶的下标:注意下标从0开始
	inline static size_t Index(size_t bytes) {
		static size_t groupArray[4] = {16, 56, 56, 56};	
		if (bytes <= 128) {
			return _Index(bytes, 8);
		}
		else if (bytes <= 1024) {
			return _Index(bytes-128, 16) + groupArray[0];
		}
		else if (bytes <= 8*1024) {
			return _Index(bytes-1024, 128) + groupArray[0] + groupArray[1];
		}
		else if (bytes <= 64*1024) {
			return _Index(bytes-8*1024, 1024) + groupArray[0] + groupArray[1] + groupArray[2];
		}
		else if (bytes <= 256*1024) {
			return _Index(bytes-64*1024, 8*1024) + groupArray[0] + groupArray[1] + groupArray[2] + groupArray[3];
		}
		else {
			assert(false);
			return -1;
		}
	}

	inline static _Index(size_t bytes, size_t alignNum) {
		size_t index = 0;
		if (bytes%alignNum != 0) {
			index = bytes/alignNum;
		}
		else {
			index = bytes/alignNum - 1; 
		}
		return index;
	}
};




















